class LockingTree
{
public:
    LockingTree(vector<int> &parent)
    {
        this->parent = parent;
        int n = parent.size();
        this->child = vector<vector<int>>(n);
        for (int i = 0; i < n; ++i)
        {
            if (parent[i] != -1)
            {
                child[parent[i]].push_back(i);
            }
        }
        this->n = n;
        this->userLock = vector<int>(n, 0);
    }

    bool lock(int num, int user)
    {
        if (userLock[num])
        {
            return false;
        }
        userLock[num] = user;
        return true;
    }

    bool unlock(int num, int user)
    {
        if (userLock[num] == user)
        {
            userLock[num] = 0;
            return true;
        }
        return false;
    }

    bool upgrade(int num, int user)
    {

        int p = num;
        while (p != -1)
        {
            if (userLock[p])
            {
                return false;
            }
            p = parent[p];
        }

        queue<int> q;
        q.push(num);

        vector<int> unlockChildren;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int v : child[u])
            {
                if (userLock[v])
                {
                    unlockChildren.push_back(v);
                }
                q.push(v);
            }
        }
        if (unlockChildren.empty())
        {
            return false;
        }
        userLock[num] = user;
        for (int v : unlockChildren)
        {
            userLock[v] = 0;
        }
        return true;
    }

private:
    vector<int> parent;
    vector<vector<int>> child;
    vector<int> userLock;
    int n;
};

/**
 * Your LockingTree object will be instantiated and called as such:
 * LockingTree* obj = new LockingTree(parent);
 * bool param_1 = obj->lock(num,user);
 * bool param_2 = obj->unlock(num,user);
 * bool param_3 = obj->upgrade(num,user);
 */